/* hashkv.c : dgnsc hash key/value map
 * Copyright (C) 2011 drangon <drangon.zhou@gmail.com>
 * 2011-09
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <dgnsc/hashkv.h>
#include <dgnsc/common.h>

#include <stddef.h> // NULL
#include <string.h>
#include <stdlib.h>

// default, key is string (char *)
unsigned int dgn_hashkv_default_hash( const void * key ) // string hash
{
	if( key == NULL )
		return 0;
	// http://www.cse.yorku.ca/~oz/hash.html  (djb2)
	const char * str = (const char *)key;
	unsigned int hash = 5381;
	int c;
	while( (c = *str++) != 0 )
		hash = ( (hash << 5) + hash ) + c; // hash * 33 + c
	return hash;
}

int dgn_hashkv_default_cmp( const void * key1, const void * key2 ) // strcmp()
{
	if( key1 == key2 )
		return 0;
	if( key1 == NULL )
		return -1;
	if( key2 == NULL )
		return 1;
	return strcmp( (char *)key1, (char *)key2 );
}

void dgn_hashkv_default_free( void * korv ) // just free()
{
	if( korv != NULL )
		free( korv );
	return;
}

struct dgn_hashkv_item_st
{
	void * key;
	void * value;

	unsigned int hash;
	struct dgn_hashkv_item_st * prev;
	struct dgn_hashkv_item_st * next;
};

struct dgn_hashkv_st
{
	int item_num;
	int prime_idx;
	struct dgn_hashkv_item_st ** hash_box; // hash array, size is s_prime[prime_idx] 
	struct dgn_hashkv_item_st hash_list;

	dgn_hashkv_hash_func_t hash_fn;
	dgn_hashkv_cmp_func_t cmp_fn;
	dgn_hashkv_freek_func_t freek_fn;
	dgn_hashkv_freev_func_t freev_fn;
};

static const unsigned int s_prime[] = {
	13, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
	49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
	12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
	805306457, 1610612741
};

dgn_hashkv_t dgn_hashkv_init( dgn_hashkv_hash_func_t hash_fn, 
		dgn_hashkv_cmp_func_t cmp_fn, dgn_hashkv_freek_func_t freek_fn,
		dgn_hashkv_freev_func_t freev_fn )
{
	if( hash_fn == NULL || cmp_fn == NULL || freek_fn == NULL || freev_fn == NULL )
		return NULL;

	struct dgn_hashkv_st * hkv = (struct dgn_hashkv_st *)malloc( sizeof(struct dgn_hashkv_st) );
	memset( hkv, 0, sizeof(*hkv) );
	hkv->hash_box = (struct dgn_hashkv_item_st **)malloc( s_prime[hkv->prime_idx] * sizeof(struct dgn_hashkv_item_st *) );
	memset( hkv->hash_box, 0, s_prime[hkv->prime_idx] * sizeof(struct dgn_hashkv_item_st *) );
	hkv->hash_list.prev = hkv->hash_list.next = &hkv->hash_list;

	hkv->hash_fn = hash_fn;
	hkv->cmp_fn = cmp_fn;
	hkv->freek_fn = freek_fn;
	hkv->freev_fn = freev_fn;
	return hkv;
}

dgn_hashkv_t dgn_hashkv_init_default()
{
	return dgn_hashkv_init( dgn_hashkv_default_hash, dgn_hashkv_default_cmp,
			dgn_hashkv_default_free, dgn_hashkv_default_free );
}

// key/value is owned and free by hashkv,
// if key exist, old key/value will be free or return
int dgn_hashkv_add( dgn_hashkv_t hkv, void * key, void * value )
{
	return dgn_hashkv_add_ex( hkv, key, value, NULL, NULL );
}

int dgn_hashkv_add_ex( dgn_hashkv_t hkv, void * key, void * value, void ** old_key, void ** old_value )
{
	if( old_key != NULL )
		*old_key = NULL;
	if( old_value != NULL )
		*old_value = NULL;
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return -1;
	}
	dgn_hashkv_iter_t iter = dgn_hashkv_iter_find( hkv, key );
	if( iter != NULL ) {
		// dgn_hashkv_iter_set( hkv, iter, value, old_value );
		if( old_key != NULL )
			*old_key = iter->key;
		else
			(hkv->freek_fn)( iter->key );
		iter->key = key;
		if( old_value != NULL )
			*old_value = iter->value;
		else
			(hkv->freev_fn)( iter->value );
		iter->value = value;
		return 0;
	}

	// do rehash if item too much
	if( hkv->item_num > s_prime[hkv->prime_idx] ) {
		struct dgn_hashkv_item_st new_list;
		hkv->prime_idx += 1;
		free( hkv->hash_box );
		hkv->hash_box = (struct dgn_hashkv_item_st **)malloc( s_prime[hkv->prime_idx] * sizeof(struct dgn_hashkv_item_st *) );
		memset( hkv->hash_box, 0, s_prime[hkv->prime_idx] * sizeof(struct dgn_hashkv_item_st *) );
		new_list.prev = new_list.next = &new_list;

		iter = hkv->hash_list.next;
		while( iter != &hkv->hash_list ) {
			struct dgn_hashkv_item_st * tmp = iter;
			iter = iter->next;

			int idx = tmp->hash % s_prime[hkv->prime_idx];
			struct dgn_hashkv_item_st * ins_pos = hkv->hash_box[idx];
			if( ins_pos == NULL )
				ins_pos = &new_list;
			tmp->next = ins_pos;
			tmp->prev = ins_pos->prev;
			tmp->next->prev = tmp;
			tmp->prev->next = tmp;
			hkv->hash_box[idx] = tmp;
		}
		hkv->hash_list.next = new_list.next;
		hkv->hash_list.prev = new_list.prev;
		hkv->hash_list.next->prev = &hkv->hash_list;
		hkv->hash_list.prev->next = &hkv->hash_list;
	}

	unsigned int hash = (hkv->hash_fn)(key);
	struct dgn_hashkv_item_st * tmp = (struct dgn_hashkv_item_st *)malloc( sizeof(struct dgn_hashkv_item_st) );
	tmp->key = key;
	tmp->value = value;
	tmp->hash = hash;
	tmp->next = tmp->prev = NULL;

	int idx = tmp->hash % s_prime[hkv->prime_idx];
	struct dgn_hashkv_item_st * ins_pos = hkv->hash_box[idx];
	if( ins_pos == NULL )
		ins_pos = &hkv->hash_list;
	tmp->next = ins_pos;
	tmp->prev = ins_pos->prev;
	tmp->next->prev = tmp;
	tmp->prev->next = tmp;
	hkv->hash_box[idx] = tmp;
	hkv->item_num += 1;
	return 0;
}

// set exist key, if not exist, do nothing
int dgn_hashkv_set( dgn_hashkv_t hkv, const void * key, void * value, void ** old_value )
{
	if( old_value != NULL )
		*old_value = NULL;
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return -1;
	}
	dgn_hashkv_iter_t iter = dgn_hashkv_iter_find( hkv, key );
	if( iter == NULL ) {
		return -1;
	}
	return dgn_hashkv_iter_set( hkv, iter, value, old_value );
}

// delete and free local key/value if exist, param key not touch
int dgn_hashkv_del( dgn_hashkv_t hkv, const void * key )
{
	return dgn_hashkv_del_ex( hkv, key, NULL, NULL );
}

int dgn_hashkv_del_ex( dgn_hashkv_t hkv, const void * key, void ** ret_key, void ** ret_value )
{
	if( ret_key != NULL )
		*ret_key = NULL;
	if( ret_value != NULL )
		*ret_value = NULL;
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return -1;
	}
	dgn_hashkv_iter_t iter = dgn_hashkv_iter_find( hkv, key );
	if( iter == NULL ) {
		return -1;
	}
	dgn_hashkv_iter_del( hkv, iter, ret_key, ret_value );
	return 0;
}

void dgn_hashkv_clear( dgn_hashkv_t hkv )
{
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return;
	}
	struct dgn_hashkv_item_st * iter = hkv->hash_list.next;
	while( iter != &hkv->hash_list ) {
		struct dgn_hashkv_item_st * tmp = iter;
		iter = iter->next;
		(hkv->freek_fn)( tmp->key );
		(hkv->freev_fn)( tmp->value );
		free( tmp );
	}
	hkv->hash_list.prev = hkv->hash_list.next = &hkv->hash_list;
	memset( hkv->hash_box, 0, sizeof(struct dgn_hashkv_item_st *) * s_prime[hkv->prime_idx] );
	hkv->item_num = 0;
	return;
}

// find value, if not exist, return NULL, may be confuse
void * dgn_hashkv_get( dgn_hashkv_t hkv, const void * key )
{
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return NULL;
	}
	dgn_hashkv_iter_t iter = dgn_hashkv_iter_find( hkv, key );
	if( iter == NULL )
		return NULL;
	return dgn_hashkv_iter_get( hkv, iter );
}

int dgn_hashkv_item_num( dgn_hashkv_t hkv )
{
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return 0;
	}
	return hkv->item_num;
}

// iterator, NULL means not exist, be invalid if call above modify func
// because item with same hash is connect sequence, and add may rehash
dgn_hashkv_iter_t dgn_hashkv_iter_next( dgn_hashkv_t hkv, dgn_hashkv_iter_t iter )
{
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return NULL;
	}
	if( iter == NULL )
		iter = &hkv->hash_list;
	iter = iter->next;
	if( iter == &hkv->hash_list )
		return NULL;
	return iter;
}

dgn_hashkv_iter_t dgn_hashkv_iter_find( dgn_hashkv_t hkv, const void * key )
{
	if( hkv == NULL ) {
		PR_DEBUG( "hkv is NULL" );
		return NULL;
	}
	unsigned int hash = (hkv->hash_fn)( key );
	int idx = hash % s_prime[hkv->prime_idx];
	struct dgn_hashkv_item_st * iter = hkv->hash_box[idx];
	for( iter = hkv->hash_box[idx]; iter != NULL && iter != &hkv->hash_list && (iter->hash % s_prime[hkv->prime_idx]) == idx; iter = iter->next ) {
		if( (hkv->cmp_fn)( key, iter->key ) == 0 )
			return iter;
	}
	return NULL;
}

void * dgn_hashkv_iter_get_key( dgn_hashkv_t hkv, dgn_hashkv_iter_t iter )
{
	if( hkv == NULL || iter == NULL ) {
		PR_DEBUG( "hkv is NULL or iter is NULL" );
		return NULL;
	}
	return iter->key;
}

void * dgn_hashkv_iter_get( dgn_hashkv_t hkv, dgn_hashkv_iter_t iter )
{
	if( hkv == NULL || iter == NULL ) {
		PR_DEBUG( "hkv is NULL or iter is NULL" );
		return NULL;
	}
	return iter->value;
}

int dgn_hashkv_iter_set( dgn_hashkv_t hkv, dgn_hashkv_iter_t iter, void * value, void ** old_value )
{
	if( old_value != NULL )
		*old_value = NULL;
	if( hkv == NULL || iter == NULL ) {
		PR_DEBUG( "hkv is NULL or iter is NULL" );
		return -1;
	}
	if( old_value != NULL )
		*old_value = iter->value;
	else
		(hkv->freev_fn)( iter->value );
	iter->value = value;
	return 0;
}

dgn_hashkv_iter_t dgn_hashkv_iter_del( dgn_hashkv_t hkv, dgn_hashkv_iter_t iter, void ** ret_key, void ** ret_value )
{
	if( ret_key != NULL )
		*ret_key = NULL;
	if( ret_value != NULL )
		*ret_value = NULL;
	if( hkv == NULL || iter == NULL ) {
		PR_DEBUG( "hkv is NULL or iter is NULL" );
		return NULL;
	}
	
	struct dgn_hashkv_item_st * iter_next = iter->next;
	if( iter_next == &hkv->hash_list )
		iter_next = NULL;

	int idx = iter->hash % s_prime[hkv->prime_idx];
	if( hkv->hash_box[idx] == iter ) {
		if( iter->next != &hkv->hash_list && (iter->next->hash % s_prime[hkv->prime_idx]) == idx )
			hkv->hash_box[idx] = iter->next;
		else
			hkv->hash_box[idx] = NULL;
	}
	iter->prev->next = iter->next;
	iter->next->prev = iter->prev;

	if( ret_key != NULL )
		*ret_key = iter->key;
	else
		(hkv->freek_fn)( iter->key );
	if( ret_value != NULL )
		*ret_value = iter->value;
	else
		(hkv->freev_fn)( iter->value );
	free( iter );
	hkv->item_num -= 1;
	return iter_next;
}

void dgn_hashkv_fini( dgn_hashkv_t hkv )
{
	if( hkv == NULL ) {
		return;
	}
	dgn_hashkv_clear( hkv );
	free( hkv->hash_box );
	free( hkv );
	return;
}

